{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Typescript: Complex Data Types, JSON, FP processing of JSON\n",
    "### PPL 2020 http://www.cs.bgu.ac.il/~ppl202\n",
    "\n",
    "On the basis of the distinction atomic types / compound types, we can define more complex data types - that embed recursively\n",
    "maps and arrays.  We introduce **Javascript Object Notation (JSON)** which has become a common language to \n",
    "exchange complex data values across systems (for example, between a client and a server or to store values in databases).  \n",
    "\n",
    "We present the different types of JSON values and finally, we describe how **higher-order functional patterns** make processing of JSON values convenient and expressive."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Literal Expressions in Programming Languages\n",
    "\n",
    "In general, programming languages provide ways to specify values as part of expressions. \n",
    "**Literal expressions** are the syntactic representation of values that appear as part of expressions.\n",
    "\n",
    "For example, consider the expression:\n",
    "```\n",
    "let v = 42;\n",
    "    (v > 0) ? \"ok\" : \"nok\";\n",
    "```\n",
    "\n",
    "In this compound expression, the sub-expressions `42`, `0`, `\"ok\"` and `\"nok\"` are all syntactic representations of \n",
    "primitive values.  These expressions are string encodings of values each according to the rules of the \n",
    "syntax of the language and to the type of the value (number, string, boolean).\n",
    "\n",
    "Distinguish between **literal expressions** and the **values** they represent:\n",
    "* **Literal expressions** are part of the syntax of a programming language; they are evaluated.\n",
    "* **Values** are the result of the evaluation; they are part of the semantics of the language.\n",
    "\n",
    "All programming languages provide syntax to write literal expressions for **atomic values**.\n",
    "\n",
    "For compound values, languages like Java and C++ provide no or very limited ways to specify literal expressions.\n",
    "For example, in Java to bind a list to its value, the following syntax must be used:\n",
    "\n",
    "```\n",
    "ArrayList<String> names = new ArrayList<String>(Arrays.asList(\"avi\", \"bob\", \"chloe\"));\n",
    "```\n",
    "\n",
    "In contrast, in JavaScript, one would write directly a compound array values as:\n",
    "```\n",
    "let names = [\"avi\", \"bob\", \"chloe\"];\n",
    "```\n",
    "\n",
    "The key difference is that the Java expression is an invocation of constructor methods, while in JavaScript compound values can be written directly.  This difference becomes more significant as we consider even more complex value types."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complex Data Values in JavaScript\n",
    "\n",
    "By combining arrays and maps, one can construct expressive data structures in JavaScript.\n",
    "For example, we can encode values such as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ name: 'PPL',\n",
       "  dept: { name: 'CS', faculty: 'Natural Sciences' },\n",
       "  students: [ { name: 'avi', age: 25 }, { name: 'beate', age: 23 } ] }"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let person1 = {name:\"avi\", age:25},\n",
    "    person2 = {name:\"beate\", age:23},\n",
    "    csDept = { name:\"CS\", faculty:\"Natural Sciences\"},\n",
    "    course = { name:\"PPL\", dept:csDept, students:[person1, person2]}\n",
    "  course"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also write this value directly, without building it \"piece by piece\" as a compound literal value expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'avi'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let ppl = { \n",
    "  name: 'PPL',\n",
    "  dept: { name: 'CS', faculty: 'Natural Sciences' },\n",
    "  students: [ { name: 'avi', age: 25 }, { name: 'beate', age: 23 } ] };\n",
    "    ppl.students[0].name;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In contrast, in Java, we would have to construct this complex value by invoking `new` on each sub-component, then consruct the value bottom up until the toplevel expression.  We would also need to define classes to describe the type of each subexpression - `Person`, `Dept`, `Course`.\n",
    "\n",
    "```\n",
    "class Person { private String name; private int age; ...}\n",
    "class Dept { private String name; private String faculty; ...}\n",
    "class Course { private String name; private Dept dept; private ArrayList<Person> students; ...\n",
    "    public void addStudent(Persont p) { students.add(p); }\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        Person person1 = new Person(\"avi\", 25);\n",
    "        Person person2 = new Person(\"beate\", 23);\n",
    "        Dept csDept = new Dept(\"cs\", \"Natural Sciences\");\n",
    "        Course ppl = new Course(\"ppl\", csDept);\n",
    "        ppl.addStudent(person1);\n",
    "        ppl.addStudent(person2);\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "The JavaScript handling of complex literal values is more concise.\n",
    "Conciseness is important because it *encourages the programmer* to use the facility.\n",
    "\n",
    "But the main difference is that complex data structures can be defined without having to define each unit as a new type - they come with less \"baggage\".  The key benefit of the easy manipulation of complex values is that different processes can exchange complex values without sharing code.  In JavaScript, this is enabled by the JSON interface."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The JSON Interface\n",
    "\n",
    "JSON stands for Java Script Object Notation.\n",
    "It is a standard way to serialize JavaScript compound values into strings and vice-versa, parse JSON strings into compound JavaScript values.\n",
    "\n",
    "The key difference between the way we described the encoding of compound literal expressions above and JSON is that:\n",
    "* Compound literal expressions are part of the syntax of the JavaScript language.  A compound literal expression is a sub-expression of a JavaScript program - which when it is evaluated yields a compound value.  Compound literal expressions are read by the parser of the programming language when a program is loaded, interpreted or compiled.\n",
    "* JSON is a runtime mechanism which permits a process to read and write compound values (from files or from sockets).\n",
    "\n",
    "JSON plays a central role in all data exchange in client-server communication, and serialization of values in databases.\n",
    "JSON is supported in a wide range of programming languages - not only in JavaScript. There are JSON libraries in Java, C++, Python etc.  \n",
    "JSON plays a role similar to XML in enabling data exchange across heterogeneous processes.\n",
    "\n",
    "The key parts of JSON are the `stringify()` and `parse()` methods which form the JSON interface."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{\"name\":\"Yosi\",\"age\":31,\"city\":\"Beer Sheva\"}\n",
      "person1JSON is of type string\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let person1 = { name : \"Yosi\", age : 31, city : \"Beer Sheva\" },\n",
    "    person1JSON = JSON.stringify(person1);\n",
    "  console.log(person1JSON)\n",
    "  console.log(`person1JSON is of type ${typeof person1JSON}`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{ name: 'Yosi', age: 31, city: 'Beer Sheva' }\n",
      "person2 is of type object\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let person2 = JSON.parse(person1JSON)\n",
    "  console.log(person2)\n",
    "  console.log(`person2 is of type ${typeof person2}`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### JSON Syntax\n",
    "\n",
    "The JSON syntax (which means the way complex values are serialized into strings) is a bit more \"strict\" than the syntax in JavaScript maps: all keys must be written with double quotes so that you need to write `{ \"a\":1 }` and not `{ a:1 }`.\n",
    "\n",
    "The JSON notation supports values of the following data types:\n",
    "* string\n",
    "* number\n",
    "* boolean\n",
    "* null\n",
    "* maps whose key values are JSON objects (recursively)\n",
    "* array of JSON values (recursively)\n",
    "\n",
    "In JavaScript, values can be all of the above, plus any other valid JavaScript expression, including:\n",
    "* functions\n",
    "* undefined\n",
    "\n",
    "The JSON interface defines the following two methods:\n",
    "* `JSON.stringify(o)` maps a value to a string.\n",
    "* `JSON.parse(s)` maps a string (written according to the JSON syntax) to a value.\n",
    "\n",
    "`JSON.stringify()` and `JSON.parse()` also work on atomic values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number\n",
      "boolean\n",
      "string\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "console.log(typeof(JSON.parse('2')))\n",
    "console.log(typeof(JSON.parse('true')))\n",
    "console.log(typeof(JSON.parse('\"abc\"')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Complex Compound Data\n",
    "\n",
    "We have described compound data as data combined using two *container* types - arrays and maps.\n",
    "\n",
    "These two container types can be **combined in a recursive manner** - so that arrays can contain other arrays or maps,\n",
    "and maps can contain other maps or arrays recursively.\n",
    "\n",
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let dept = {\"deptName\":\"accounting\",\n",
    "            \"employees\": [\n",
    "                    { \"firstName\":\"John\", \"lastName\":\"Doe\" },\n",
    "                    { \"firstName\":\"Anna\", \"lastName\":\"Smith\" },\n",
    "                    { \"firstName\":\"Peter\", \"lastName\":\"Jones\" }\n",
    "                ]};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `dept` value is a map which has a key `employees` with a value which is an embedded array whose items are nested maps.\n",
    "\n",
    "To take apart the components of this value, the getters can be combined:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'John'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dept.employees[0].firstName"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Doe'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dept[\"employees\"][0][\"lastName\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, arrays can contain nested arrays or maps.\n",
    "\n",
    "**JavaScript Arrays are heterogeneous** - they can contain items of different types."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "heteroArr contains items of the following types: \n",
      "number\n",
      "boolean\n",
      "string\n",
      "nestedArr contains items of the following types: \n",
      "number\n",
      "object\n",
      "object\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let heteroArr = [1, true, \"a\"],\n",
    "    nestedArr = [1, [2, 3], {a:1, b:2}]\n",
    "  console.log(\"heteroArr contains items of the following types: \")\n",
    "  heteroArr.forEach(x => console.log(typeof x))\n",
    "  console.log(\"nestedArr contains items of the following types: \")\n",
    "  nestedArr.forEach(x => console.log(typeof x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Map and Array Mutators\n",
    "\n",
    "In JavaScript, compound values are **mutable**.  This means that, in addition to accessing parts of a compound value, JavaScript allows us:\n",
    "* to change the value of components of a larger compound value and \n",
    "* to remove components of larger compound values.\n",
    "\n",
    "The fact that variables and the basic data types in JavaScript are mutable makes *real* functional programming difficult - since FP requires variables and compound data structures to be immutable.  There are libraries, though, that enable the definition of immutable data structures and their efficient manipulation - such as https://facebook.github.io/immutable-js/."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ deptName: 'accounting',\n",
       "  employees: \n",
       "   [ { firstName: 'John', lastName: 'Doe' },\n",
       "     { firstName: 'Anna', lastName: 'Smith' },\n",
       "     { firstName: 'Peter', lastName: 'Jones' } ] }"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dept"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'programming'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dept.deptName = 'programming'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "delete(dept.employees[0].lastName)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ deptName: 'programming',\n",
       "  employees: \n",
       "   [ { firstName: 'John' },\n",
       "     { firstName: 'Anna', lastName: 'Smith' },\n",
       "     { firstName: 'Peter', lastName: 'Jones' } ] }"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dept"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 1, 2 ]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let mutableArr = [0, 1, 2]\n",
    "  mutableArr[0] = 1\n",
    "  mutableArr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Array Primitive Mutators\n",
    "\n",
    "JavaScript Arrays have many built-in primitives that allow mutation or copy of array values.\n",
    "It is sometimes difficult to keep track of which operations modify the array (mutators) and which operations\n",
    "create new array values.\n",
    "\n",
    "For example, `sort()` and `reverse()` are mutators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1, 2, 3, 4, 5 ]\n",
      "[ 1, 2, 3, 4, 5 ]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let a1 = [1,5,3,2,4]\n",
    "    console.log(a1.sort())\n",
    "    console.log(a1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you see above, after the `sort()` method is invoked on an array, the array is modified in place.\n",
    "`sort()` is a mutator.  Similarly, `reverse()` is a mutator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 4, 3, 2, 1 ]\n",
      "[ 4, 3, 2, 1 ]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let a2 = [1,2,3,4]\n",
    "    console.log(a2.reverse())\n",
    "    console.log(a2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The methods `push()` and `pop()` are also mutators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4 ]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4, 5 ]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The methods `shift()` and `unshift()` are similar to `pop()` and `push()` but operate on the beginning of the array (while push and pop operate on the end of the array). They are also mutators:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1.shift()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 2, 3, 4, 5 ]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1.unshift(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4, 5 ]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In contrast, the `concat()` method returns a copy of the original arrays and does not modifiy its arguments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4, 5, 4, 3, 2, 1 ]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1.concat(a2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1, 2, 3, 4, 5 ]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 4, 3, 2, 1 ]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Useful Array Methods\n",
    "\n",
    "The following methods are included in the Array interface:\n",
    "* `length`: returns the number of elements in the array\n",
    "* `includes(x)`: returns true if x is an element in the array, false otherwise\n",
    "* `indexOf(x)`: returns the index of x within the array, -1 if x is not in the array\n",
    "* `join(delimiter)`: returns a string with all the items of the array serialized with delimiter between them.\n",
    "* `slice(start, end)`: returns a shallow copy of a sub-sequence from the array.\n",
    "* `splice(index)`: splits the array at the index position, and returns the suffix of the array after index (mutator)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "am has 6 items\n",
      "am.includes(2) is true\n",
      "am.indexOf(2) is 1\n",
      "am.join() is 1,2,3,4,5,6\n",
      "am.slice(2,4) is 3,4\n",
      "am.splice(2) is 3,4,5,6\n",
      "am is [1,2] after splice(2)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let am = [1,2,3,4,5,6]\n",
    "    console.log(`am has ${am.length} items`)\n",
    "    console.log(`am.includes(2) is ${am.includes(2)}`)\n",
    "    console.log(`am.indexOf(2) is ${am.indexOf(2)}`)\n",
    "    console.log(`am.join() is ${am.join()}`)\n",
    "    console.log(`am.slice(2,4) is ${am.slice(2,4)}`)\n",
    "    console.log(`am.splice(2) is ${am.splice(2)}`)\n",
    "    console.log(`am is [${am}] after splice(2)`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Higher Order Methods on Arrays and JSON\n",
    "\n",
    "The Array interface includes higher order methods - that is, methods which receive a function as an argument.\n",
    "These methods are extremely versatile:\n",
    "* `a.sort((a,b) => a > b)`: sort the elements with the comparator passed as a parameter (mutator).\n",
    "* `a.map(x => x*x)`: return a new array of the same length as `a` [f(x) for x in a]\n",
    "* `a.filter(pred)`: return a new array with all elements `x` in `a` that satisfy `pred(x)`\n",
    "* `a.find(pred)`: return the first element `x` of `a` which satisfies `pred(x)` (similar to `filter` but returns only one item)\n",
    "* `a.findIndex(pred)`: same as `find`, but returns the position of the first item `x` in `a` which satisfies `pred(x)`\n",
    "* `a.every(pred)`: return `true` if all elements in `a` satisfy `pred`\n",
    "* `a.some(pred)`: return `true` if at least one element in `a` satisfies `pred`\n",
    "* `a.forEach(f)`: applies the function `f` on all elements of `a` - useful only when `f` has side effects. \n",
    "* `a.reduce((acc, item) => transformer, init)`: transforms the array by applying the same transformer function on each item in `a` and accumulating the successive results of the transformer.\n",
    "\n",
    "Of these many methods, the most important are:\n",
    "* `map`\n",
    "* `filter`\n",
    "* `reduce`\n",
    "\n",
    "The importance of these functions is that they allow us to manipulate complex values as a whole, instead of writing code\n",
    "that iterates (loops) over each item.  This gives a declarative flavor to the code that manipulates JSON values - similar\n",
    "to SQL over relational data.\n",
    "\n",
    "Consider the following example JSON value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "undefined"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const people = [\n",
    "  {\n",
    "    name: 'Avi',\n",
    "    age: 23,\n",
    "    gender: 'm',\n",
    "    cs: true\n",
    "  },\n",
    "  {\n",
    "    name: 'Ben',\n",
    "    age: 25,\n",
    "    gender: 'm',\n",
    "    cs: false,\n",
    "  },\n",
    "   {\n",
    "    name: 'Gila',\n",
    "    age: 24,\n",
    "    gender: 'f',\n",
    "    cs: true,\n",
    "  },\n",
    "   {\n",
    "    name: 'Dalia',\n",
    "    age: 27,\n",
    "    gender: 'f',\n",
    "    cs: false,\n",
    "  },\n",
    "];"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use `filter()` with appropriate predicates to perform operations similar to a `select` in SQL: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ { name: 'Avi', age: 23, gender: 'm', cs: true },\n",
       "  { name: 'Gila', age: 24, gender: 'f', cs: true } ]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Select the people who are CS students\n",
    "people.filter(p => p.cs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ { name: 'Gila', age: 24, gender: 'f', cs: true },\n",
       "  { name: 'Dalia', age: 27, gender: 'f', cs: false } ]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Select people by gender\n",
    "people.filter(p => p.gender == 'f')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map` can be used to compute transformations of the input items.\n",
    "For example, assume we want to compute the year of birth of each person, we can compute:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1995, 1993, 1994, 1991 ]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "people.map(p => 2018 - p.age)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to modify the maps of each person, we can use mutation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ { name: 'Avi', age: 23, gender: 'm', cs: true, birthYear: 1995 },\n",
       "  { name: 'Ben', age: 25, gender: 'm', cs: false, birthYear: 1993 },\n",
       "  { name: 'Gila', age: 24, gender: 'f', cs: true, birthYear: 1994 },\n",
       "  { name: 'Dalia', age: 27, gender: 'f', cs: false, birthYear: 1991 } ]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// When a fat-array function body contains more than one expression - we must put the body in {} and use \"return\"\n",
    "// When the body has only one expression, we can skip both (x => x*x)\n",
    "people.map(p => {p.birthYear = 2018-p.age; return p})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the application of a function with mutation through `map` modified the original JSON objec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ { name: 'Avi', age: 23, gender: 'm', cs: true, birthYear: 1995 },\n",
       "  { name: 'Ben', age: 25, gender: 'm', cs: false, birthYear: 1993 },\n",
       "  { name: 'Gila', age: 24, gender: 'f', cs: true, birthYear: 1994 },\n",
       "  { name: 'Dalia', age: 27, gender: 'f', cs: false, birthYear: 1991 } ]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "people"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`map()` and `filter()` return an array based on the original array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reduce\n",
    "\n",
    "The `reduce()` method transforms the array into a single value through iterative application through each item.\n",
    "It applies a function against an accumulator and each value of the array (from left-to-right) to reduce it to a single value.\n",
    "\n",
    "`reduce()` is often called `fold()` or `accumulate()` in other FP languages. \n",
    "\n",
    "It iterates over a list, applying a function to an accumulated value and the next item in the list, until the iteration is complete and the accumulated value gets returned. \n",
    "\n",
    "`reduce()` takes a reducer function and an initial value, and returns the accumulated value.\n",
    "The reducer function receives two arguments: the current accumulator and the current item.\n",
    "\n",
    "```\n",
    "array.reduce(\n",
    "  reducer: (accumulator: Any, current: Any) => Any,\n",
    "  initialValue: Any\n",
    ") => accumulator: Any\n",
    "```\n",
    "\n",
    "This is useful for any type of aggregation which would be similar to a `group by` statement in SQL over the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Sum of all elements in the array\n",
    "[2,4,6].reduce((acc, n) => acc + n, 0);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each element in the array, the reducer is called and passed the accumulator and the current value. \n",
    "The reducerג€™s job is to ג€foldג€ the current value into the accumulated value. \n",
    "The reducer returns the new accumulated value, and reduce() moves on to the next value in the array. \n",
    "The reducer needs an initial value to start with, so the initial value is passed as a parameter to `reduce()`.\n",
    "\n",
    "**NOTE**: In general, it makes sense that the initial value should be a neutral element for the accumulator function.\n",
    "\n",
    "In the case of our sum, the first time the reducer is called, acc starts with 0 - the value we passed to `reduce()` as the second parameter. \n",
    "\n",
    "The reducer returns 0 + 2 (2 was the first element in the array), which is 2. \n",
    "\n",
    "For the next call, acc = 2, n = 4 and the reducer returns the result of 2 + 4 (6). \n",
    "\n",
    "In the last iteration, acc = 6, n = 6, and the reducer returns 12. \n",
    "\n",
    "Since the iteration is finished, .reduce() returns the final accumulated value, 12.\n",
    "\n",
    "In this case, we passed in an anonymous reducing function, but we can abstract it and give it a name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const sumReducer = (acc, n) => acc + n;\n",
    "[2,4,6].reduce(sumReducer, 0);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to trace the behavior of the reducer, we can add calls to log:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reduce 0 + 2\n",
      "Reduce 2 + 4\n",
      "Reduce 6 + 6\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "const tracingSumReducer = (acc, n) => { console.log(`Reduce ${acc} + ${n}`); return acc+n; }\n",
    "[2, 4, 6].reduce(tracingSumReducer, 0);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduce can map to values of different types than those present in the array on which it iterates:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "99"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Sum age of all persons in the people array\n",
    "people.reduce((acc, p) => acc + p.age, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And reduce can return compound values as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ men: 2, women: 2 }"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Count number of men and women\n",
    "people.reduce(\n",
    "    (counter, p) => {\n",
    "        p.gender == 'm' ? counter.men++ : counter.women++;\n",
    "        return counter;\n",
    "    }, {men:0, women:0})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "### Literal Expressions and Complex Values\n",
    "* Programming languages define as part of their syntax ways to describe **literal expressions** which are evaluated to values.\n",
    "* JavaScript (and most *dynamic programming languages* which do not require type declarations for all variables) allow programmers to write **literal compound expressions** which encode compound values.\n",
    "* Compound values can be embedded recursively to yield complex data structures.\n",
    "* JavaScript variables and data structures are mutable.\n",
    "\n",
    "### JSON\n",
    "* JSON is a string serialization of JavaScript values (atomic and compound).\n",
    "* The JSON interface includes 2 functions: `JSON.stringify()` and `JSON.parse()`\n",
    "* JSON values can include embedded arrays and maps in a recursive manner - down to atomic values in the leaves.\n",
    "* JSON compound values can be taken apart using composed accessors - for example `dept.employees[0].firstName`.\n",
    "* JSON compound values can be mutated in place using composed mutators - for example, `dept.employees[0].firstName = 'avi'`\n",
    "* Components within a JSON compound value can be removed using the `delete()` operator.\n",
    "* Arrays include primitive methods to access and mutate them: `length, includes(x), indexOf(x), join(delimiter), slice(start, end), splice(index)`.\n",
    "* Arrays include higher-order methods which receive functions as parameters.  In particular, `map(), filter()` and `reduce()` are extremely useful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "\n",
    "### Map, Filter, Reduce\n",
    "\n",
    "1. Define a function `product(arrayNumbers)` which returns the product of all the numbers in an array of numbers.\n",
    "**Example:**\n",
    "```\n",
    "product([1,2,3]) -> 6\n",
    "```\n",
    "What should be the value of product([])? Justify.\n",
    "\n",
    "2. Using the Ramda function range (http://ramdajs.com/docs/#range) - define a version of the `factorial()` function using\n",
    "`reduce()`.\n",
    "```\n",
    "import * as R from 'ramda'; \n",
    "R.range(1,5)\n",
    "[ 1,2,3,4 ]\n",
    "```\n",
    "3. Define `map()` using `reduce()`.\n",
    "\n",
    "4. Define `filter()` using `reduce()`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### JSON\n",
    "\n",
    "1. Run the exercises in http://reactivex.io/learnrx/ \n",
    "   \n",
    "2. Consider the following JSON value (obtained from a call to a Netflix API):\n",
    "\n",
    "```\n",
    "let movieLists = [\n",
    "\t\t{\n",
    "\t\t\tname: \"New Releases\",\n",
    "\t\t\tvideos: [\n",
    "\t\t\t\t{\n",
    "\t\t\t\t\t\"id\": 70111470,\n",
    "\t\t\t\t\t\"title\": \"Die Hard\",\n",
    "\t\t\t\t\t\"boxart\": \"http://cdn-0.nflximg.com/images/2891/DieHard.jpg\",\n",
    "\t\t\t\t\t\"uri\": \"http://api.netflix.com/catalog/titles/movies/70111470\",\n",
    "\t\t\t\t\t\"rating\": 4.0,\n",
    "\t\t\t\t\t\"bookmark\": []\n",
    "\t\t\t\t},\n",
    "\t\t\t\t{\n",
    "\t\t\t\t\t\"id\": 654356453,\n",
    "\t\t\t\t\t\"title\": \"Bad Boys\",\n",
    "\t\t\t\t\t\"boxart\": \"http://cdn-0.nflximg.com/images/2891/BadBoys.jpg\",\n",
    "\t\t\t\t\t\"uri\": \"http://api.netflix.com/catalog/titles/movies/70111470\",\n",
    "\t\t\t\t\t\"rating\": 5.0,\n",
    "\t\t\t\t\t\"bookmark\": [{ id: 432534, time: 65876586 }]\n",
    "\t\t\t\t}\n",
    "\t\t\t]\n",
    "\t\t},\n",
    "\t\t{\n",
    "\t\t\tname: \"Dramas\",\n",
    "\t\t\tvideos: [\n",
    "\t\t\t\t{\n",
    "\t\t\t\t\t\"id\": 65432445,\n",
    "\t\t\t\t\t\"title\": \"The Chamber\",\n",
    "\t\t\t\t\t\"boxart\": \"http://cdn-0.nflximg.com/images/2891/TheChamber.jpg\",\n",
    "\t\t\t\t\t\"uri\": \"http://api.netflix.com/catalog/titles/movies/70111470\",\n",
    "\t\t\t\t\t\"rating\": 4.0,\n",
    "\t\t\t\t\t\"bookmark\": []\n",
    "\t\t\t\t},\n",
    "\t\t\t\t{\n",
    "\t\t\t\t\t\"id\": 675465,\n",
    "\t\t\t\t\t\"title\": \"Fracture\",\n",
    "\t\t\t\t\t\"boxart\": \"http://cdn-0.nflximg.com/images/2891/Fracture.jpg\",\n",
    "\t\t\t\t\t\"uri\": \"http://api.netflix.com/catalog/titles/movies/70111470\",\n",
    "\t\t\t\t\t\"rating\": 5.0,\n",
    "\t\t\t\t\t\"bookmark\": [{ id: 432534, time: 65876586 }]\n",
    "\t\t\t\t}\n",
    "\t\t\t]\n",
    "\t\t}\n",
    "\t]\n",
    "```\n",
    "\n",
    "This JSON value is a sort of **tree** with two levels - with a list of video objects at the 2nd level.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using only `map(), filter()` and `reduce()` - compute the following values:\n",
    "* The number of movies in the \"Dramas\" category\n",
    "* The number of movies (in all categories)\n",
    "* The list of the names and urls of movies with a rating of 5.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Typescript 2.9",
   "language": "typescript",
   "name": "typescript"
  },
  "language_info": {
   "file_extension": ".ts",
   "mimetype": "text/x-typescript",
   "name": "typescript",
   "version": "2.9.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}